import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//TIP To <b>Run</b> code, press <shortcut actionId="Run"/> or
// click the <icon src="AllIcons.Actions.Execute"/> icon in the gutter.
class Solution {
    private List<List<String>> ret = new ArrayList<>();
    //这个相当于3维数组
    public List<List<String>> solveNQueens(int n) {
        //这里注意是二维数组
        //我们要利用回溯算法
        //因为题目只给出了一个整数
        //所以我们要自定义一个二维数组
        char[][] chessboard = new char[n][n];
        for (char[] c : chessboard) {
            //初始胡棋盘
            Arrays.fill(c, '.');
        }

        backTracking(n , 0, chessboard);
        System.out.println(ret.size());
        return ret;
    }

    private void backTracking(int n, int row, char[][] chessboard) {
        //我们每次从不同行开始遍历
        //但是每次都从第0列开始遍历
        //很明显，在叶子结点时收货结果
        if (row == n) {
            ret.add(Array2List(chessboard));
            return;
        }

        //直接遍历列，每次从0开始
        for (int i = 0; i < n; i++) {
            //因为行已经确定了
            //这里直接判断是否合法
            if (isValid(row, i, n, chessboard)) {
                //此时相当于这一行里面只放了一个皇后
                //之后就去了下一行
                chessboard[row][i] = 'Q';
                backTracking(n, row + 1, chessboard);
                chessboard[row][i] = '.';//回溯
            } else {
                //此时位置不合法，跳过当前列
                continue;
            }
        }
    }

    private List<String> Array2List(char[][] chessboard) {
        List<String> list = new ArrayList<>();

        for (char[] c : chessboard) {
            list.add(String.copyValueOf(c));
        }

        return list;
    }

    private boolean isValid(int row, int col, int n, char[][] chessboard) {
        //检查列
        for (int i = 0; i < row; i++) {
            if (chessboard[i][col] == 'Q') {
                return false;
            }
        }

        //检查45度对角线
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }

        //检查135度对角线
        for (int i = row - 1, j = col + 1; i >= 0 && j <= n - 1; i--, j++) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }

        //这里不用检查行，因为我们每一行就放一个皇后之后就换行了
        return true;
    }
}



public class Main {
    public static void main(String[] args) {
        int[] a = new int[3];
        for (int i = 0; i < 3; i++) {
            System.out.println(a[i]);
        }
        boolean[] judge = new boolean[5];
        for (int i = 0; i < 5; i++) {
            System.out.println(judge[i]);
            System.out.println("真的累，");
        }
    }
    public static void main4(String[] args) {
        System.out.println("好了好了，今天要刷4道题，任务艰巨，还要补课！");
    }
    public static void main3(String[] args) {
        int a = 2, b = 3;
        int d;
        StringBuilder str = new StringBuilder();
        str.append("avc");
        System.out.println(str);
        str.append("bcd");
        System.out.println(str);
        System.out.println(str.toString().getClass());
        System.out.println(str.getClass());
        String sr = "abcd";
        System.out.println(sr.substring(0, sr.length() - 1));
        int c = Integer.MAX_VALUE;
        System.out.println(Math.abs(a - b));
        System.out.println("搞我是吧？？？");
        System.out.println("今天是补课，还行");
        System.out.println("我不知道在干嘛？");
    }
    public static void main2(String[] args) {
        System.out.println("好难啊，真的好难啊！");
        System.out.println("无数次想过放弃，真的好难啊！");
    }
    public static void main1(String[] args) {
        System.out.println("太爽了！");
        System.out.println("不会吧？");
        Solution solution = new Solution();
        List<List<String>> list = solution.solveNQueens(4);
        System.out.println(list.size());
    }
}